λ¬Έμ
π Logic
public void insert(String word) {
TrieNode thisNode = this.rootNode;
for (int i = 0; i < word.length(); i++) {
thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
thisNode.size++;
}
}
-
λ¨μ΄λ₯Ό ν κΈμμ©
Trieμ μΆκ°νλ€.- μ΄λ λλ€μμ μ΄μ©νμ¬ μΆκ°νλλ‘ νλ€.
- μΆκ°ν λλ§λ€, ν΄λΉ λ¨μ΄κ° μ¬μ©λλ νμλ₯Ό μ¦κ°μν¨λ€. (
go, gone, guildμ κ²½μ°,gμsizeλ 3μ΄λ€.)
public int findCount(String word) {
TrieNode thisNode = this.rootNode;
int count = 0;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
TrieNode node = thisNode.getChildNodes().get(c);
count++;
if (node.size == 1) break;
thisNode = node;
}
return count;
}
-
μ£Όμ΄μ§ λ¨μ΄μ
Trieλ₯Ό νμνλ©΄μ,sizeκ° 1μΈ κ²½μ°κΉμ§countλ₯Ό μ¦κ°μν¨λ€.sizeκ° 1μ΄λΌλ κ²μ κ²°κ΅ ν΄λΉ λ¬Έμλ₯Ό μ¬μ©νλ λ¨μ΄κ° 1κ°μΈ κ²½μ°μ΄κ³ , ν΄λΉ λ¬ΈμκΉμ§ μ λ ₯νλ€λ©΄ κ·Έ λ¨μ΄λ₯Ό μλμμ±μν¬ μ μλ€!
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class TrieNode {
private Map<Character, TrieNode> childNodes = new HashMap<>();
int size;
public Map<Character, TrieNode> getChildNodes() {
return this.childNodes;
}
}
class Trie {
private TrieNode rootNode;
public Trie() {
rootNode = new TrieNode();
}
public void insert(String word) {
TrieNode thisNode = this.rootNode;
for (int i = 0; i < word.length(); i++) {
thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
thisNode.size++;
}
}
public int findCount(String word) {
TrieNode thisNode = this.rootNode;
int count = 0;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
TrieNode node = thisNode.getChildNodes().get(c);
count++;
if (node.size == 1) break;
thisNode = node;
}
return count;
}
}
class Solution {
public int solution(String[] words) {
Trie t = new Trie();
for (String word : words)
t.insert(word);
int answer = 0;
for (String word : words)
answer += t.findCount(word);
return answer;
}
}
βοΈ Review
- μ²μ 보λ
Trieλ¬Έμ μ¬μ, μ΄ μλ£ κ΅¬μ‘°λ₯Ό μ΄ν΄νλ λ° μ§μ€νλ€. λ§μΉ¨ μ΄λ² μ£Ό CS μ€ν°λ λ΄μ© μ€Trieκ° μμ΄μ λ¨Όμ μ 리ν ν ꡬνν΄λ³΄μλ€. - μκ°λ³΄λ€ λ§μ΄ μ΄λ €μ΄ λ΄μ©μ μλμλ κ² κ°μ§λ§, μμ©ν΄μ λ¬Έμ λ₯Ό νΈλ λ°λ μ’ κ±Έλ Έλ€.